#include "AI.h"
#include <cstdlib>
#include <cassert>
#include <cstring>
#include <string>
#include <iostream>
#include <ctime>

using namespace std;

// stores if each square is blocked

void testPerformance(Board & b, BoardState player)
{
    const int REPEAT = 10000;
    static clock_t sum1 = 0;
    static clock_t sum2 = 0;
    clock_t start;
    int count1, count2;
    int moves[100];
    BitBoard effect[100];
    
    gameState gs = parseBoard(b, BLOCKED_MAP);

    start = clock();
    for (int i = 0; i < REPEAT; i++)
    {
        const set<pair<int, int> > moves = b.legalMoves(player);
        count1 = moves.size();
        
        set<pair<int, int> >::const_iterator it = moves.begin();
        while (it != moves.end()) {
            Board temp = Board(b);
            temp.makeMove(it->first, it->second, player);
            it++;
        }
    }
    sum1 = sum1 + clock() - start;
    
    start = clock();
    for (int i = 0; i < REPEAT; i++)
    {
        count2 = getMoves(gs, BLOCKED_MAP, player, moves, effect);
        
        for (int j = 0; j < count2; j++)
        {
            gameState temp = applyMove(gs, player, moves[j], effect[moves[j]]);
        }
    }
    sum2 = sum2 + clock() - start;
    
    
    // check the number of moves is the same
    assert(count1 == count2);
    
    // check the resulting board are the same
    const set<pair<int, int> > move_pairs = b.legalMoves(player);
    count2 = getMoves(gs, BLOCKED_MAP, player, moves, effect);
    set<pair<int, int> >::const_iterator it = move_pairs.begin();
    
    while (it != move_pairs.end())
    {
        Board temp = Board(b);
        temp.makeMove(it->first, it->second, player);
        
        int index = it->first + it->second * 10;
        
        // assert each move is the same
        bool isIn = false;
        for (int i = 0; i < count2; i++)
        {
            if (moves[i] == index)
                isIn = true;
        }
        assert(isIn);
        
        gameState temp_gs = applyMove(gs, player, index, effect[index]);
        
        gameState temp_gs2 = parseBoard(temp, BLOCKED_MAP);
        
        assert(temp_gs == temp_gs2);
        it++;
    }
    
    cout << "array representation:     " << sum1 << endl;
    cout << "bit board representation: " << sum2 << endl;
}

void quickSort(int moves[], gameState children[], int score[], int beg, int end)
{
    int t_score, t_m;
    gameState t_gs;
    
    if (end > beg + 1)
    {
        int piv = score[beg], l = beg + 1, r = end;
        while (l < r)
        {
            if (score[l] >= piv)
                l++;
            else
            {
                r--;
                swap(score[l], score[r], t_score);
                swap(children[l], children[r], t_gs);
                swap(moves[l], moves[r], t_m);
            }
        }
        l--;
        swap(score[l], score[beg], t_score);
        swap(children[l], children[beg], t_gs);
        swap(moves[l], moves[beg], t_m);
        quickSort(moves, children, score, beg, l);
        quickSort(moves, children, score, r, end);
    }
}
/* order moves using the best n policy
   #in, out# moves      ... input list of moves and output a reordered list
   #in, out# child      ... child game after each move has been applied
   #in#      mCount     ... number of moves
   #in#      player     ... the current player
   #in#      stage      ... stage the game is at                            */
void OrderMoves(int moves[], gameState children[], int mCount, BoardState player, int stage)
{
    int score[100];
    for (int i = 0; i < mCount; i++)
    {
        if (player == WHITE)
            score[i] = evaluateGame(children[i], player, stage);
        else
            score[i] = -evaluateGame(children[i], player, stage);
        
    }
    
    quickSort(moves, children, score, 0, mCount);
}

/* Compute negamax score for the node
   #in#  node       ... current game state
   #in#  player     ... player to move
   #in#  depth      ... depth of the subtree
   #in#  alpha      ... lower bound for optimum score
   #in#  beta       ... upper bound for optimum score
   #in#  stage      ... which stage the game is at (= number of pieces - 5)
   #in#  pass_move  ... whether the previous player passed his move
   return           ... minimax score of the current node                   */
int NegaScout(gameState node, BoardState player, int depth, int alpha, int beta, int stage, bool pass_move)
{
    if (stage == 92)
    {
        if (player == WHITE)
            return evaluateTerminal(node);
        else
            return -evaluateTerminal(node);
    }
    if (depth <= 0)
    {
        int value = evaluateGame(node, player, stage);
        if (player == WHITE)
            return value; 
        else
            return -value; 
    }
    
    int _moves[100];
    BitBoard _effects[100];
    gameState _children[100];
    
    int _mCount = getMoves(node, BLOCKED_MAP, player, _moves, _effects);
    int b = beta;    
    BoardState next_player = player == BLACK ? WHITE : BLACK;
    
    // if current player has no move
    if (_mCount == 0)
    {
        // neither player has move, we reached pass_move position
        if (pass_move)
        {
            if (player == WHITE)
                return evaluateTerminal(node);
            else
                return -evaluateTerminal(node);
        }
        else
            return -NegaScout(node, next_player, depth, -beta, -alpha, stage, true);
    }
    
    // build children
    for (int i = 0; i < _mCount; i++)
    {
        _children[i] = applyMove(node, player, _moves[i], _effects[_moves[i]]);
    }
    
    if (depth >= TRIVIAL_DEPTH)
    {
        OrderMoves(_moves, _children, _mCount, player, stage+1);
    }
    
    // otherwise
    depth--;
    for (int i = 0; i < _mCount; i++)
    {
        int score = -NegaScout(_children[i], next_player, depth, -b, -alpha, stage + 1, false);
        
        if (alpha < score && score < beta && i != 0)
        {
            score = -NegaScout(_children[i], next_player, depth, -beta, -alpha, stage + 1, false);
        }
        
        if (score > alpha)
        {
            alpha = score;
        }
        
        if (alpha >= beta)
        {
            return alpha;
        }
        
        b = alpha + 1;
    }
    
    return alpha;
}


int NegaScoutEndGame(gameState node, BoardState player, int alpha, int beta, int stage, bool pass_move)
{
    if (stage == 92)
    {
        if (player == WHITE) return evaluateTerminal(node);
        else                 return -evaluateTerminal(node);
    }
    
    int moves[100];
    BitBoard effects[100];
    
    int mCount = getMoves(node, BLOCKED_MAP, player, moves, effects);
    
    BoardState next_player = player == WHITE ? BLACK : WHITE;
    if (mCount == 0)
    {
        if (pass_move)
        {
            if (player == WHITE) return evaluateTerminal(node);
            else                 return -evaluateTerminal(node);
        }
        else
        {
            return -NegaScoutEndGame(node, next_player, -beta, -alpha, stage, true);
        }
    }
    // increment depth count
    stage++;
    // build list of children
    gameState children[100];
    for (int i = 0; i < mCount; i++)
        children[i] = applyMove(node, player, moves[i], effects[moves[i]]); 
    
    if (91 - stage >= END_GAME_TRIVIAL_DEPTH)
        OrderMoves(moves, children, mCount, player, stage);
    
    // perform negascout search
    int b = beta;
    for (int i = 0; i < mCount; i++)
    {
        int score = -NegaScoutEndGame(children[i], next_player, -b, -alpha, stage, false);
        
        if (alpha < score && score < beta && i != 0)
            score = -NegaScoutEndGame(children[i], next_player, -beta, -alpha, stage, false);
        
        if (score > alpha) alpha = score;
        if (alpha >= beta) return alpha;
        
        b = alpha + 1;  
    }
    return alpha;
}

/* solve the end game */
int SolveEndGame(gameState gs, BoardState player, int stage)
{
    int moves[100];
    BitBoard effects[100];
    int mCount = getMoves(gs, BLOCKED_MAP, player, moves, effects);
    
    int best_move = 0;
    int alpha = -INFINITY;
    int beta = INFINITY;
    BoardState next_player = player == WHITE ? BLACK : WHITE;
    
    int b = beta;

    
    // build list of children
    stage++;
    gameState children[100];
    for (int i = 0; i < mCount; i++)
        children[i] = applyMove(gs, player, moves[i], effects[moves[i]]); 
    
    if (91 - stage >= END_GAME_TRIVIAL_DEPTH)
        OrderMoves(moves, children, mCount, player, stage);
    
    for (int i = 0; i < mCount; i++)
    {   
        int score = -NegaScoutEndGame(children[i], next_player, -b, -alpha, stage, false);
        
        if (alpha < score && score < beta && i != 0)
            score = -NegaScoutEndGame(children[i], next_player, -beta, -alpha, stage, false);
        
        if (score > alpha)
        {
            alpha = score;
            best_move = moves[i];
        }
        if (alpha >= beta) break;
        
        b = alpha + 1;
    }
    return best_move;
}
    
/* choose the best move 
   #in#  board      ... current board state
   #in#  player     ... current player
   return           ... best move (x, y) in the format x*10 + y             */
int chooseMove(Board & board, BoardState player, int depth, int end_game)
{
    int moves[100], best_move, mCount, stage;
    BitBoard effects[100];
    gameState gs = parseBoard(board, BLOCKED_MAP);
    

    stage = BitCount(gs.white | gs.black) - 5;
    
    if (stage >= 91 - end_game)
    {
        return SolveEndGame(gs, player, stage);
    }
    mCount = getMoves(gs, BLOCKED_MAP, player, moves, effects);
    int alpha = -INFINITY;
    int beta = INFINITY;
    BoardState next_player = player == WHITE ? BLACK : WHITE;
    
    // build children
    gameState children[100];
    for (int i = 0; i < mCount; i++)
    {
        children[i] = applyMove(gs, player, moves[i], effects[moves[i]]);
    }
    
    if (depth >= TRIVIAL_DEPTH)
    {
        OrderMoves(moves, children, mCount, player, stage+1);
    }
    
    int b = beta;
    depth--;   
    for (int i = 0; i < mCount; i++)
    {   
        int score = -NegaScout(children[i], next_player, depth, -b, -alpha, stage + 1, false);
        
        if (alpha < score && score < beta && i != 0)
        {
            score = -NegaScout(children[i], next_player, depth, -beta, -alpha, stage+1, false);
        }
        
        if (alpha < score)
        {
            best_move = moves[i];
            alpha = score;
        }
        if (alpha >= beta)
            break;
            
        b = alpha + 1;
    }

	return best_move;
}

void initialiseAI()
{
    initialiseMasks();
    initialiseEvaluator();
}
